#ifndef BINARYTREE
#define BINARYTREE
template<typename TValue>
class BinaryTree
{
public:
	enum class ChildSide { Left, Right, };
	using Side = ChildSide;
	using ValueType = TValue;
private:
	BinaryTree* pLeft;
	BinaryTree* pRight;
	BinaryTree* pBase;
	Side side;// 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义；不应由自己修改，而应由双亲修改
	int count;
public:
	TValue Value;
public:
	// 构造只有一个节点的树，并且元素为默认值
	BinaryTree();
	// 用指定值构造只有一个节点的树
	BinaryTree(const TValue& value);
	// 构造一个树，根节点的元素为指定值，并指定一个子树
	BinaryTree(const TValue& value, BinaryTree* pChild, Side side);
	// 构造一个树，根节点的元素为指定值，并指定左右两个子树
	BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild);
	// 析构该树及其所有子树
	~BinaryTree();
	BinaryTree(const BinaryTree&) = delete;
	// 接管一个树，被接管的树成为一个孤立的节点
	BinaryTree(BinaryTree&& other);
	// 获取该树的双亲的指针
	BinaryTree* Parent();
	// 获取左子树的指针
	BinaryTree* LeftChild();
	// 获取右子树的指针
	BinaryTree* RightChild();
	// 获取节点总数
	int Count();
	// 获取树的深度
	int DepthToLeaf();
	// 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义
	Side SideOfParent();
	// 设置指定子树，先前的子树会被析构
	void SetChild(BinaryTree* pChild, Side side);
	// 删除指定子树，将其析构
	void RemoveChild(Side side);
	// 移除指定子树，但不会析构该子树，而是返回指向它的指针
	BinaryTree* ReleaseChild(Side side);
	BinaryTree* ReleaseChild(BinaryTree* pChild);
};

template<typename TValue>
BinaryTree<TValue>::BinaryTree()
{
	this->pLeft = nullptr;
	this->pRight = nullptr;
	this->pBase = nullptr;
	this->count = 1;
	this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value)
{
	this->pLeft = nullptr;
	this->pRight = nullptr;
	this->pBase = nullptr;
	this->Value = value;
	this->count = 1;
	this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pChild, Side side)
{
	switch (side)
	{
	case Side::Left:
	{
		this->pLeft = pChild;
		pChild->side = Side::Left;
		this->pRight = nullptr;
		break;
	}
	case Side::Right:
	{
		this->pRight = pChild;
		pChild->side = Side::Right;
		this->pLeft = nullptr;
		break;
	}
	default:
		break;
	}
	pChild->pBase = this;
	this->Value = value;
	this->count = 1 + pChild->count;
	this->pBase = nullptr;
	this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild)
{
	this->pLeft = pLChild;
	pLChild->side = Side::Left;
	this->pRight = pRChild;
	pRChild->side = Side::Right;
	this->pBase = nullptr;
	pLChild->pBase = this;
	pRChild->pBase = this;
	this->Value = value;
	this->count = 1 + pLChild->count + pRChild->count;
}

template<typename TValue>
BinaryTree<TValue>::~BinaryTree()
{
	delete this->pLeft;
	delete this->pRight;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(BinaryTree&& other)
{
	this->pBase = other.pBase;
	this->pLeft = other.pLeft;
	this->pRight = other.pRight;
	this->count = other.count;
	this->side = other.side;
	this->Value = other.Value;
	if (this->pLeft != nullptr)
	{
		this->pLeft->pBase = this;
	}
	if (this->pRight != nullptr)
	{
		this->pRight->pBase = this;
	}
	if (this->pBase != nullptr)
	{
		switch (this->side)
		{
		case Side::Left:
		{
			this->pBase->pLeft = this;
			break;
		}
		case Side::Right:
		{
			this->pBase->pRight = this;
			break;
		}
		default:
			break;
		}
	}
	other.pBase = nullptr;
	other.pLeft = nullptr;
	other.pRight = nullptr;
	other.count = 1;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::Parent()
{
	return this->pBase;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::LeftChild()
{
	return this->pLeft;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::RightChild()
{
	return this->pRight;
}

template<typename TValue>
int BinaryTree<TValue>::Count()
{
	return this->count;
}

template<typename TValue>
int BinaryTree<TValue>::DepthToLeaf()
{
	int leftDepth = 0, rightDepth = 0;
	if (this->LeftChild() != nullptr)
	{
		leftDepth = this->LeftChild()->DepthToLeaf();
	}
	if (this->RightChild() != nullptr)
	{
		rightDepth = this->RightChild()->DepthToLeaf();
	}
	if (leftDepth >= rightDepth)
	{
		return leftDepth + 1;
	}
	else
	{
		return rightDepth + 1;
	}
}

template<typename TValue>
typename BinaryTree<TValue>::Side BinaryTree<TValue>::SideOfParent()
{
	return this->side;
}

template<typename TValue>
void BinaryTree<TValue>::SetChild(BinaryTree* pChild, Side side)
{
	switch (side)
	{
	case Side::Left:
	{
		if (this->pLeft != nullptr)
		{
			this->count -= this->pLeft->count;
			delete this->pLeft;
			this->pLeft = nullptr;
		}
		if (pChild != nullptr)
		{
			this->pLeft = pChild;
			pChild->pBase = this;
			pChild->side = Side::Left;
			this->count += pChild->count;
		}
		break;
	}
	case Side::Right:
	{
		if (this->pRight != nullptr)
		{
			this->count -= this->pRight->count;
			delete this->pRight;
			this->pRight = nullptr;
		}
		if (pChild != nullptr)
		{
			this->pRight = pChild;
			pChild->pBase = this;
			pChild->side = Side::Right;
			this->count += pChild->count;
		}
		break;
	}
	default:
		break;
	}
}

template<typename TValue>
void BinaryTree<TValue>::RemoveChild(Side side)
{
	switch (side)
	{
	case Side::Left:
	{
		if (this->pLeft != nullptr)
		{
			this->count -= this->pLeft->count;
			delete this->pLeft;
			this->pLeft = nullptr;
		}
		break;
	}
	case Side::Right:
	{
		if (this->pRight != nullptr)
		{
			this->count -= this->pRight->count;
			delete this->pRight;
			this->pRight = nullptr;
		}
		break;
	}
	default:
		break;
	}
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(Side side)
{
	BinaryTree* pTree = nullptr;
	switch (side)
	{
	case Side::Left:
	{
		if (this->pLeft != nullptr)
		{
			this->count -= this->pLeft->count;
			pTree = this->pLeft;
			this->pLeft = nullptr;
		}
		break;
	}
	case Side::Right:
	{
		if (this->pRight != nullptr)
		{
			this->count -= this->pRight->count;
			pTree = this->pRight;
			this->pRight = nullptr;
		}
		break;
	}
	default:
		break;
	}
	if (pTree != nullptr)
	{
		pTree->pBase = nullptr;
	}
	return pTree;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(BinaryTree* pChild)
{
	if (pChild == nullptr)
	{
		return nullptr;
	}
	if (pChild->pBase != this)
	{
		return nullptr;
	}
	return this->ReleaseChild(pChild->side);
}

#endif // !BINARYTREE

#ifndef ARRAY
#define ARRAY
#ifndef REVERSED_ITERATOR
#define REVERSED_ITERATOR
// 将一个顺序访问的迭代器包装成反向迭代器
template<typename TSequentialAccessIterator>
class ReversedSequentailAccessIterator
{
private:
	TSequentialAccessIterator* pIterator;
public:
	ReversedSequentailAccessIterator(TSequentialAccessIterator& it);
	ReversedSequentailAccessIterator(const ReversedSequentailAccessIterator& other);
	~ReversedSequentailAccessIterator();
public:
	using ValueType = typename TSequentialAccessIterator::ValueType;
	// 前置++
	ReversedSequentailAccessIterator& operator++() noexcept;
	// 前置--
	ReversedSequentailAccessIterator& operator--() noexcept;
	bool operator==(const ReversedSequentailAccessIterator& other) const noexcept;
	bool operator!=(const ReversedSequentailAccessIterator& other) const noexcept;
	ValueType& operator*();
	ValueType* operator->();
	operator TSequentialAccessIterator();
};

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::ReversedSequentailAccessIterator(TSequentialAccessIterator& it)
{
	this->pIterator = new TSequentialAccessIterator(it);
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::ReversedSequentailAccessIterator(const ReversedSequentailAccessIterator& other)
{
	this->pIterator = new TSequentialAccessIterator(*other.pIterator);
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::~ReversedSequentailAccessIterator()
{
	delete this->pIterator;
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator++() noexcept
{
	--(*this->pIterator);
	return *this;
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator--() noexcept
{
	++(*this->pIterator);
	return *this;
}

template<typename TSequentialAccessIterator>
bool ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator==(const ReversedSequentailAccessIterator& other) const noexcept
{
	return *this->pIterator == *other.pIterator;
}

template<typename TSequentialAccessIterator>
bool ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator!=(const ReversedSequentailAccessIterator& other) const noexcept
{
	return *this->pIterator != *other.pIterator;
}

template<typename TSequentialAccessIterator>
typename ReversedSequentailAccessIterator<TSequentialAccessIterator>::ValueType& ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator*()
{
	return *(*this->pIterator);
}

template<typename TSequentialAccessIterator>
typename ReversedSequentailAccessIterator<TSequentialAccessIterator>::ValueType* ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator->()
{
	return (*this->pIterator).operator->();
}

template<typename TSequentialAccessIterator>
ReversedSequentailAccessIterator<TSequentialAccessIterator>::operator TSequentialAccessIterator()
{
	return *this->pIterator;
}


// 将一个随机访问迭代器包装成反向迭代器
template<typename TRandomAccessIterator>
class ReversedRandomAccessIterator
{
private:
	TRandomAccessIterator* pIterator;
public:
	ReversedRandomAccessIterator(TRandomAccessIterator& it);
	ReversedRandomAccessIterator(const ReversedRandomAccessIterator& other);
	~ReversedRandomAccessIterator();
public:
	using ValueType = typename TRandomAccessIterator::ValueType;
	// 前置++
	ReversedRandomAccessIterator& operator++() noexcept;
	// 前置--
	ReversedRandomAccessIterator& operator--() noexcept;
	// 随机访问
	ReversedRandomAccessIterator operator+(int offset) noexcept;
	ReversedRandomAccessIterator operator-(int offset) noexcept;
	bool operator==(const ReversedRandomAccessIterator& other) const noexcept;
	bool operator!=(const ReversedRandomAccessIterator& other) const noexcept;
	ValueType& operator*();
	ValueType* operator->();
	operator TRandomAccessIterator();
};

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::ReversedRandomAccessIterator(TRandomAccessIterator& it)
{
	this->pIterator = new TRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::ReversedRandomAccessIterator(const ReversedRandomAccessIterator& other)
{
	this->pIterator = new TRandomAccessIterator(*other.pIterator);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::~ReversedRandomAccessIterator()
{
	delete this->pIterator;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>& ReversedRandomAccessIterator<TRandomAccessIterator>::operator++() noexcept
{
	--(*this->pIterator);
	return *this;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>& ReversedRandomAccessIterator<TRandomAccessIterator>::operator--() noexcept
{
	++(*this->pIterator);
	return *this;
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator> ReversedRandomAccessIterator<TRandomAccessIterator>::operator+(int offset) noexcept
{
	TRandomAccessIterator it((*this->pIterator) - offset);
	return ReversedRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator> ReversedRandomAccessIterator<TRandomAccessIterator>::operator-(int offset) noexcept
{
	TRandomAccessIterator it((*this->pIterator) + offset);
	return ReversedRandomAccessIterator(it);
}

template<typename TRandomAccessIterator>
bool ReversedRandomAccessIterator<TRandomAccessIterator>::operator==(const ReversedRandomAccessIterator& other) const noexcept
{
	return *this->pIterator == *other.pIterator;
}

template<typename TRandomAccessIterator>
bool ReversedRandomAccessIterator<TRandomAccessIterator>::operator!=(const ReversedRandomAccessIterator& other) const noexcept
{
	return *this->pIterator != *other.pIterator;
}

template<typename TRandomAccessIterator>
typename ReversedRandomAccessIterator<TRandomAccessIterator>::ValueType& ReversedRandomAccessIterator<TRandomAccessIterator>::operator*()
{
	return *(*this->pIterator);
}

template<typename TRandomAccessIterator>
typename ReversedRandomAccessIterator<TRandomAccessIterator>::ValueType* ReversedRandomAccessIterator<TRandomAccessIterator>::operator->()
{
	return (*this->pIterator).operator->();
}

template<typename TRandomAccessIterator>
ReversedRandomAccessIterator<TRandomAccessIterator>::operator TRandomAccessIterator()
{
	return *this->pIterator;
}



#endif // !REVERSED_ITERATOR


template<typename TValue>
class Array
{
private:
	// 默认容量使得内部申请的数组为4096字节
	static constexpr int DefaultLength = 4096 / sizeof(TValue);
	static constexpr int DefaultCapacity = DefaultLength - 2;
public:
	using ExceptionType = int;
	using ValueType = TValue;
	static constexpr ExceptionType OutOfRange = -1;
public:
	// 构造一个具有指定初始容量的Array
	Array(int initCapacity = DefaultCapacity);
	// 使用一个范围进行构造，包括begin但不包括end
	template<typename TIterator>
	Array(TIterator beginIt, TIterator endIt, int initCapacity = DefaultCapacity);
	// 析构
	~Array();
	// 复制
	Array(Array& other);
	// 移动
	Array(Array&& other);
	// 赋值
	Array& operator=(Array& other);
	Array& operator=(Array&& other);

	class ArrayIterator;
	using ReversedArrayIterator = ReversedRandomAccessIterator<ArrayIterator>;
	class ArrayIterator
	{
	public:
		using ValueType = TValue;
		// 前置++
		ArrayIterator& operator++() noexcept;
		// 前置--
		ArrayIterator& operator--() noexcept;
		// 随机访问
		ArrayIterator operator+(int offset) noexcept;
		ArrayIterator operator-(int offset) noexcept;
		bool operator==(const ArrayIterator& other) const noexcept;
		bool operator!=(const ArrayIterator& other) const noexcept;
		TValue& operator*();
		TValue* operator->();
		operator ReversedArrayIterator();
		ArrayIterator(ReversedArrayIterator& rIt);
	private:
		friend class Array;
		ArrayIterator(TValue* pValue);
		TValue* pValue;
	};

public:
	// 直接随机访问, 索引从0开始
	TValue& operator[](int index);
	// 获取迭代器
	ArrayIterator Begin();
	ArrayIterator End();
	ReversedArrayIterator ReversedBegin();
	ReversedArrayIterator ReversedEnd();
	// 在it之前插入value, 并且返回指向插入的值的iterator
	ArrayIterator Insert(const TValue& value, ArrayIterator&& it);
	ArrayIterator Insert(const TValue& value, ArrayIterator& it);
	// 在最后插入
	ArrayIterator InsertBack(const TValue& value);
	// 在开头插入
	ArrayIterator InsertFront(const TValue& value);
	// 移除it, 并且返回it原先的后继iterator
	ArrayIterator Remove(ArrayIterator&& it);
	ArrayIterator Remove(ArrayIterator& it);
	// 删除所有某个元素， 返回删除的个数
	template<typename TComparator>
	int RemoveAll(const TValue& value, TComparator compare);
	// 查找value, 并且返回指向value的iterator, 如果找不到则返回End()
	template<typename TComparator>
	ArrayIterator Find(const TValue value, TComparator compare);
	// 将容量缩减至当前元素个数
	void Shrink();
	// 获取实际存储的元素个数
	int Count();
private:
	TValue* pArray;
	int capacity; // 容量等于pArray的长度-2
	int count;
	int beginIndex;
	int endIndex;
};

template<typename TValue>
Array<TValue>::Array(int initCapacity)
{
	this->capacity = initCapacity;
	this->pArray = new TValue[initCapacity + 2];
	this->beginIndex = this->capacity / 4;
	this->endIndex = this->beginIndex + 1;
	this->count = 0;
}

template<typename TValue>
template<typename TIterator>
Array<TValue>::Array(TIterator beginIt, TIterator endIt, int initCapacity)
{
	this->capacity = initCapacity;
	this->pArray = new TValue[initCapacity + 2];
	this->beginIndex = this->capacity / 4;
	this->endIndex = this->beginIndex + 1;
	this->count = 0;
	for (auto it = beginIt; it != endIt; ++it)
	{
		this->InsertBack(*it);
	}
}


template<typename TValue>
Array<TValue>::~Array()
{
	delete[] this->pArray;
}

template<typename TValue>
Array<TValue>::Array(Array& other)
{
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = new TValue[this->capacity + 2];
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	for (int i = this->beginIndex; i <= this->endIndex; ++i)
	{
		this->pArray[i] = other.pArray[i];
	}
}

template<typename TValue>
Array<TValue>::Array(Array&& other)
{
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = other.pArray;
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	other.pArray = nullptr;
}

template<typename TValue>
Array<TValue>& Array<TValue>::operator=(Array& other)
{
	delete[] this->pArray;
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = new TValue[this->capacity + 2];
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	for (int i = this->beginIndex; i <= this->endIndex; ++i)
	{
		this->pArray[i] = other.pArray[i];
	}
	return *this;
}

template<typename TValue>
Array<TValue>& Array<TValue>::operator=(Array&& other)
{
	delete[] this->pArray;
	this->capacity = other.capacity;
	this->count = other.count;
	this->pArray = other.pArray;
	other.pArray = nullptr;
	this->beginIndex = other.beginIndex;
	this->endIndex = other.endIndex;
	return *this;
}

template<typename TValue>
TValue& Array<TValue>::operator[](int index)
{
	if (index < 0 || index >= this->count)
	{
		throw Array::OutOfRange;
	}
	return this->pArray[this->beginIndex + index + 1];
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Begin()
{
	return ArrayIterator(this->pArray + this->beginIndex + 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::End()
{
	return ArrayIterator(this->pArray + this->endIndex);
}

template<typename TValue>
typename Array<TValue>::ReversedArrayIterator Array<TValue>::ReversedBegin()
{
	ArrayIterator rbegin(this->pArray + this->endIndex - 1);
	return ReversedArrayIterator(rbegin);
}

template<typename TValue>
typename Array<TValue>::ReversedArrayIterator Array<TValue>::ReversedEnd()
{
	ArrayIterator rend(this->pArray + this->beginIndex);
	return ReversedArrayIterator(rend);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Insert(const TValue& value, ArrayIterator&& it)
{
	return this->Insert(value, it);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Insert(const TValue& value, ArrayIterator& it)
{
	if (it == this->End())
	{
		return this->InsertBack(value);
	}
	else if (it == this->Begin())
	{
		return this->InsertFront(value);
	}
	// 往中间插入，计算it距离哪头近，就移动那边元素
	int insertIndex = it.pValue - this->pArray;
	int direction = 1; // 1表示移动右边
	if (insertIndex - this->beginIndex <= this->endIndex - insertIndex)
	{
		direction = 0; // 0表示移动左边
	}

	// 待移动的方向到达了边界，则触发扩展，这时要复制所有元素，因此行为是一致的
	if ((direction == 1 && this->endIndex == this->capacity + 1) || (direction == 0 && this->beginIndex == 0))
	{
		// 复制到插入位置之前，然后加入新元素，再继续复制
		int newCapacity = this->capacity + DefaultLength;
		TValue* pNewArray = new TValue[newCapacity + 2];
		// 如果是向左扩展，则元素从新数组的DefaultLength - 2索引开始存放，否则从原先的索引开始进行存放
		int newBeginIndex = this->beginIndex;
		if (direction == 0)
		{
			newBeginIndex = DefaultLength - 2;
		}
		int idx = newBeginIndex + 1;
		auto i = this->Begin();
		auto end = this->End();
		for (; i != it; ++i)
		{
			pNewArray[idx] = *i;
			++idx;
		}
		pNewArray[idx] = value;
		auto pos = pNewArray + idx;
		++idx;
		while (i != end)
		{
			pNewArray[idx] = *i;
			++i;
			++idx;
		}
		delete[] this->pArray;
		this->pArray = pNewArray;
		this->capacity = newCapacity;
		this->count++;
		this->beginIndex = newBeginIndex;
		this->endIndex = newBeginIndex + this->count + 1;
		return ArrayIterator(pos);
	}
	// 不需要扩展，仅移动元素
	else if (direction == 1)
	{
		// 向右移动
		auto fastIt = this->End() - 1;
		auto slowIt = this->End();
		while (slowIt != it)
		{
			*slowIt = *fastIt;
			--slowIt;
			--fastIt;
		}
		*slowIt = value;
		this->count++;
		this->endIndex++;
		return slowIt;
	}
	else if (direction == 0)
	{
		// 向左移动
		auto fastIt = this->Begin();
		auto slowIt = this->Begin() - 1;
		while (slowIt != it)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		*slowIt = value;
		this->count++;
		this->beginIndex--;
		return slowIt;
	}
	else
	{

	}
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::InsertBack(const TValue& value)
{
	// 右侧到头，触发扩展
	if (this->endIndex == this->capacity + 1)
	{
		TValue* pNewArray = new TValue[this->capacity + 2 + DefaultLength];
		for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
		{
			pNewArray[i] = this->pArray[i];
		}
		delete this->pArray;
		this->pArray = pNewArray;
		this->capacity += DefaultLength;
	}
	this->pArray[this->endIndex] = value;
	this->count += 1;
	this->endIndex += 1;
	return ArrayIterator(this->pArray + this->endIndex - 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::InsertFront(const TValue& value)
{
	// 左侧到头，触发扩展
	if (this->beginIndex == 0)
	{
		TValue* pNewArray = new TValue[this->capacity + 2 + DefaultLength];
		for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
		{
			pNewArray[i + DefaultLength] = this->pArray[i];
		}
		delete this->pArray;
		this->pArray = pNewArray;
		this->capacity += DefaultLength;
		this->beginIndex += DefaultLength;
	}
	this->pArray[this->beginIndex] = value;
	this->count += 1;
	this->beginIndex -= 1;
	return ArrayIterator(this->pArray + this->beginIndex + 1);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Remove(ArrayIterator&& it)
{
	return this->Remove(it);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::Remove(ArrayIterator& it)
{
	int direction = 1; // 1表示移动右边
	auto originPos = it.pValue; // 如果移动右边，则原先的位置就变成后继
	int insertIndex = it.pValue - this->pArray;
	if (insertIndex - this->beginIndex <= this->endIndex - insertIndex)
	{
		direction = 0; // 0表示移动左边
		++originPos;
	}
	if (direction == 1)
	{
		auto slowIt = it;
		auto fastIt = slowIt + 1;
		auto endIt = this->End();
		while (fastIt != endIt)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		this->count--;
		this->endIndex--;
	}
	else
	{
		auto slowIt = ReversedArrayIterator(it);
		auto fastIt = slowIt + 1;
		auto endIt = this->ReversedEnd();
		while (fastIt != endIt)
		{
			*slowIt = *fastIt;
			++slowIt;
			++fastIt;
		}
		this->count--;
		this->beginIndex++;
	}
	return ArrayIterator(originPos);
}

template<typename TValue>
template<typename TComparator>
int Array<TValue>::RemoveAll(const TValue& value, TComparator compare)
{
	int numToRemove = 0;
	int* indexToRemove = new int[this->count];
	for (int i = this->beginIndex + 1; i < this->endIndex; ++i)
	{
		if (compare(value, this->pArray[i]) == 0)
		{
			indexToRemove[numToRemove] = i;
			++numToRemove;
		}
	}
	if (numToRemove == 0)
	{
		delete[] indexToRemove;
		return 0;
	}
	int removed = 0;
	for (int i = indexToRemove[0]; i <= this->endIndex - 1 - numToRemove; ++i)
	{
		while (i + removed == indexToRemove[removed] && removed < numToRemove)
		{
			++removed;
		}
		this->pArray[i] = this->pArray[i + removed];
	}

	delete[] indexToRemove;
	this->count -= numToRemove;
	this->endIndex -= numToRemove;
	return numToRemove;
}

template<typename TValue>
template<typename TComparator>
typename Array<TValue>::ArrayIterator Array<TValue>::Find(const TValue value, TComparator compare)
{
	auto it = this->Begin();
	auto end = this->End();
	while (it != end)
	{
		if (compare(*it, value) == 0)
		{
			break;
		}
		++it;
	}
	return it;
}


template<typename TValue>
void Array<TValue>::Shrink()
{
	constexpr int NotImplemeted = -2;
	throw NotImplemeted;
}

template<typename TValue>
int Array<TValue>::Count()
{
	return this->count;
}



template<typename TValue>
Array<TValue>::ArrayIterator::ArrayIterator(TValue* pValue)
{
	this->pValue = pValue;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator& Array<TValue>::ArrayIterator::operator++() noexcept
{
	++this->pValue;
	return *this;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator& Array<TValue>::ArrayIterator::operator--() noexcept
{
	--this->pValue;
	return *this;
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::ArrayIterator::operator+(int offset) noexcept
{
	return ArrayIterator(this->pValue + offset);
}

template<typename TValue>
typename Array<TValue>::ArrayIterator Array<TValue>::ArrayIterator::operator-(int offset) noexcept
{
	return ArrayIterator(this->pValue - offset);
}

template<typename TValue>
bool Array<TValue>::ArrayIterator::operator==(const ArrayIterator& other) const noexcept
{
	return this->pValue == other.pValue;
}

template<typename TValue>
bool Array<TValue>::ArrayIterator::operator!=(const ArrayIterator& other) const noexcept
{
	return this->pValue != other.pValue;
}

template<typename TValue>
TValue& Array<TValue>::ArrayIterator::operator*()
{
	return *this->pValue;
}

template<typename TValue>
TValue* Array<TValue>::ArrayIterator::operator->()
{
	return this->pValue;
}

template<typename TValue>
Array<TValue>::ArrayIterator::operator ReversedArrayIterator()
{
	return ReversedArrayIterator(*this);
}

template<typename TValue>
Array<TValue>::ArrayIterator::ArrayIterator(ReversedArrayIterator& rIt)
{
	this->pValue = ((ArrayIterator)rIt).pValue;
}

#endif // !ARRAY

#ifndef QUEUE
#define QUEUE
template<typename TContainer>
class Queue
{
public:
	using ValueType = typename TContainer::ValueType;
	using ExceptionType = int;
	static constexpr int NoCapacityLimit = -1;
	static constexpr ExceptionType QueueEmpty = -1;
	static constexpr ExceptionType QueueFull = -2;
public:
	Queue(int capacity = NoCapacityLimit);
	Queue(const Queue&) = delete;
	Queue(Queue&&) = delete;
	~Queue();
	int Count();
	ValueType DeQueue();
	ValueType& Front();
	ValueType& Rear();
	void EnQueue(const ValueType& value);
	void Clear();
private:
	TContainer* pContainer;
	int capacity;
};

template<typename TContainer>
Queue<TContainer>::Queue(int capacity)
{
	this->capacity = capacity;
	this->pContainer = new TContainer();
}

template<typename TContainer>
Queue<TContainer>::~Queue()
{
	delete this->pContainer;
}

template<typename TContainer>
int Queue<TContainer>::Count()
{
	return this->pContainer->Count();
}

template<typename TContainer>
typename Queue<TContainer>::ValueType Queue<TContainer>::DeQueue()
{
	if (this->Count() == 0)
	{
		throw QueueEmpty;
	}
	ValueType value = *(this->pContainer->Begin());
	this->pContainer->Remove(this->pContainer->Begin());
	return value;
}

template<typename TContainer>
typename Queue<TContainer>::ValueType& Queue<TContainer>::Front()
{
	if (this->Count() == 0)
	{
		throw QueueEmpty;
	}
	return *(this->pContainer->Begin());
}

template<typename TContainer>
typename Queue<TContainer>::ValueType& Queue<TContainer>::Rear()
{
	if (this->Count() == 0)
	{
		throw QueueEmpty;
	}
	return *(this->pContainer->ReversedBegin());
}

template<typename TContainer>
void Queue<TContainer>::EnQueue(const ValueType& value)
{
	if (this->Count() == this->capacity)
	{
		throw QueueFull;
	}
	this->pContainer->Insert(value, this->pContainer->End());
}

template<typename TContainer>
void Queue<TContainer>::Clear()
{
	delete this->pContainer;
	this->pContainer = new TContainer();
}

#endif // !QUEUE


#include <iostream>
#include <string>


using Tree = BinaryTree<char>;

struct TreeMapItem
{
	char Value;
	int LeftIndex;
	int RightIndex;
	Tree* pItem;
};

Tree* ReadTree()
{
	int count;
	std::cin >> count;
	if (count == 0)
	{
		return nullptr;
	}

	TreeMapItem* map = new TreeMapItem[count];
	// 读取
	for (int i = 0; i < count; ++i)
	{
		std::cin >> map[i].Value;
		std::string val;
		std::cin >> val;
		if (val == "-")
		{
			map[i].LeftIndex = -1;
		}
		else
		{
			map[i].LeftIndex = std::stoi(val);
		}
		std::cin >> val;
		if (val == "-")
		{
			map[i].RightIndex = -1;
		}
		else
		{
			map[i].RightIndex = std::stoi(val);
		}
		map[i].pItem = nullptr;
	}

	// 生成
	for (int i = 0; i < count; ++i)
	{
		if (map[i].pItem == nullptr)
		{
			map[i].pItem = new Tree(map[i].Value);
		}
		int leftIndex = map[i].LeftIndex;
		if (leftIndex != -1)
		{
			if (map[leftIndex].pItem == nullptr)
			{
				map[leftIndex].pItem = new Tree(map[leftIndex].Value);
			}
			map[i].pItem->SetChild(map[leftIndex].pItem, Tree::Side::Left);
		}
		int rightIndex = map[i].RightIndex;
		if (rightIndex != -1)
		{
			if (map[rightIndex].pItem == nullptr)
			{
				map[rightIndex].pItem = new Tree(map[rightIndex].Value);
			}
			map[i].pItem->SetChild(map[rightIndex].pItem, Tree::Side::Right);
		}
	}

	// 返回
	Tree* pTree = map[0].pItem;
	while (pTree->Parent() != nullptr)
	{
		pTree = pTree->Parent();
	}
	return pTree;
}


bool JudgeIsostructure(Tree* tree1, Tree* tree2, int& depth)
{
	if (tree1 == nullptr)
	{
		if (tree2 == nullptr)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	if (tree2 == nullptr)
	{
		return false;
	}
	if (tree1->Count() != tree2->Count())
	{
		return false;
	}
	depth = tree1->DepthToLeaf();
	if (depth != tree2->DepthToLeaf())
	{
		return false;
	}
	if (tree1->Value != tree2->Value)
	{
		return false;
	}
	Queue<Array<Tree*>> q1, q2;
	q1.EnQueue(tree1);
	q2.EnQueue(tree2);
	while (q1.Count() != 0)
	{
		Tree* node1 = q1.DeQueue();
		Tree* node2 = q2.DeQueue();

		Tree* l1 = node1->LeftChild();
		Tree* l2 = node2->LeftChild();
		Tree* r1 = node1->RightChild();
		Tree* r2 = node2->RightChild();

		// 两个节点的两个孩子均为空
		if (l1 == nullptr && r1 == nullptr)
		{
			if (l2 == nullptr && r2 == nullptr)
			{
				continue;
			}
			else
			{
				return false;
			}
		}

		// 两个节点的都只有一个孩子
		if (l1 == nullptr)
		{
			if (l2 == nullptr && r2 == nullptr)
			{
				return false;
			}
			if (l2 == nullptr)
			{
				if (r1->Value == r2->Value)
				{
					q1.EnQueue(r1);
					q2.EnQueue(r2);
					continue;
				}
				else
				{
					return false;
				}
			}
			else if (r2 == nullptr)
			{
				if (r1->Value == l2->Value)
				{
					q1.EnQueue(r1);
					q2.EnQueue(l2);
					continue;
				}
				else
				{
					return false;
				}
			}
			else
			{
				return false;
			}
		}
		else if (r1 == nullptr)
		{
			if (l2 == nullptr && r2 == nullptr)
			{
				return false;
			}
			if (l2 == nullptr)
			{
				if (l1->Value == r2->Value)
				{
					q1.EnQueue(l1);
					q2.EnQueue(r2);
					continue;
				}
				else
				{
					return false;
				}
			}
			else if (r2 == nullptr)
			{
				if (l1->Value == l2->Value)
				{
					q1.EnQueue(l1);
					q2.EnQueue(l2);
					continue;
				}
				else
				{
					return false;
				}
			}
			else
			{
				return false;
			}
		}

		// 两个节点都有两个孩子
		if (l2 == nullptr || r2 == nullptr)
		{
			return false;
		}
		if (l1->Value == l2->Value && r1->Value == r2->Value) // 有bug：四个子节点都相等，但需要交换后同构，这里可能判断为不同构
		{
			q1.EnQueue(l1);
			q2.EnQueue(l2);
			q1.EnQueue(r1);
			q2.EnQueue(r2);
			continue;
		}
		else if (l1->Value == r2->Value && r1->Value == l2->Value)
		{
			q1.EnQueue(l1);
			q2.EnQueue(r2);
			q1.EnQueue(r1);
			q2.EnQueue(l2);
			continue;
		}
		else
		{
			return false;
		}
	}

}

bool RecursionJudgeIsostructure(Tree* tree1, Tree* tree2)
{
	if (tree1 == nullptr)
	{
		if (tree2 == nullptr)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	if (tree2 == nullptr)
	{
		return false;
	}
	if (tree1->Value != tree2->Value)
	{
		return false;
	}
	if (RecursionJudgeIsostructure(tree1->LeftChild(), tree2->LeftChild())
		&& RecursionJudgeIsostructure(tree1->RightChild(), tree2->RightChild()))
	{
		return true;
	}
	if (RecursionJudgeIsostructure(tree1->LeftChild(), tree2->RightChild())
		&& RecursionJudgeIsostructure(tree1->RightChild(), tree2->LeftChild()))
	{
		return true;
	}
	return false;
}

void PrintPreorder(Tree& tree)
{
	std::cout << tree.Value;
	if (tree.LeftChild() != nullptr)
	{
		PrintPreorder(*tree.LeftChild());
	}
	if (tree.RightChild() != nullptr)
	{
		PrintPreorder(*tree.RightChild());
	}
}

int main()
{
	Tree* tree1 = ReadTree();
	Tree* tree2 = ReadTree();

	std::cout << (RecursionJudgeIsostructure(tree1, tree2) ? "Yes" : "No") << std::endl;
	std::cout << tree1->DepthToLeaf() << std::endl << tree2->DepthToLeaf() << std::endl;


	return 0;
}